Curse of dimensionality reduction in max-plus based approximation methods: theoretical estimates and improved pruning algorithms

摘要

Max-plus based methods have been recently developed to approximate the valuefunction of possibly high dimensional optimal control problems. A critical stepof these methods consists in approximating a function by a supremum of a smallnumber of functions (max-plus "basis functions") taken from a prescribeddictionary. We study several variants of this approximation problem, which weshow to be continuous versions of the facility location and $k$-centercombinatorial optimization problems, in which the connection costs arise from aBregman distance. We give theoretical error estimates, quantifying the numberof basis functions needed to reach a prescribed accuracy. We derive from ourapproach a refinement of the curse of dimensionality free method introducedpreviously by McEneaney, with a higher accuracy for a comparable computationalcost.